package week_02;

import java.util.*;

public class GenerateParentheses_22_2 {

    public static Map<Integer, List<String>> h = new HashMap<>();

    public static void main(String[] args) {
        GenerateParentheses_22_2 solution = new GenerateParentheses_22_2();
        List<String> ans = solution.generateParenthesis(7);
        ans.forEach(System.out::println);
    }

    // 增加记忆化 加快速度
    public List<String> generateParenthesis(int n) {
        if (h.containsKey(n)) return h.get(n);

        if (n == 0) {
            h.put(0, Arrays.asList(""));
            return Arrays.asList("");
        } else {
            List<String> ans = new ArrayList<>();
            for (int k = 0; k < n; k++) {
                List<String> aps = generateParenthesis(k);
                List<String> bps = generateParenthesis(n - k - 1);
                for (String ap : aps) {
                    for (String bp : bps) {
                        ans.add("(" + ap + ")" + bp);
                    }
                }

            }
            h.put(n, ans);
            return ans;
        }

    }
}
